package algorithm.leetcode.I101to200;

import algorithm.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径
 * 思想: 递归
 *
 * 注意是递归不是回溯,在每个recursive中分叉出两个分支向下
 */

public class Q113 {
    public List<List<Integer>> results = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        dfs(root, new LinkedList<>(), sum);
        return results;
    }


    public void dfs(TreeNode node,
                    LinkedList<Integer> curr,
                    int remainLength) {
        // base case
        if (node == null) return;

        curr.addLast(node.val);
        // if & only if 当前节点是叶子节点,并且剩余的值是当前节点的值,添加临时解
        if (node.left == null && node.right == null && remainLength == node.val) {
            results.add(new LinkedList<>(curr));
        }
        dfs(node.left, curr, remainLength - node.val);
        dfs(node.right, curr, remainLength - node.val);
        curr.removeLast();
    }

    public static void main(String[] args) {
        TreeNode a = new TreeNode(3), b = new TreeNode(3), c = new TreeNode(3), d = new TreeNode(3), e = new TreeNode(2),
                f = new TreeNode(-3), g = new TreeNode(-2);
        // g.left = e;
        g.right = f;
        // e.left = c;
        // e.right = d;
        // c.left = a;
        // c.right = b;
        Q113 q113 = new Q113();
        System.out.println(q113.pathSum(g, -2));
        LinkedList<TreeNode> curr = new LinkedList<TreeNode>() {{add(f);}};

    }

}
